/* 模块：bits_indicator
 * 类型：适配器
 * 功能：通过静态分配/动态分配 bits_indicator 提供的数据，对外提供位一致的指示器基础功能
 * 用法：
 * TODO======================================================================================
 */

// 注意: 保证 u_t 是实际的存储类型，而非转换的 unsigned_type<T>，因为需要支持 lexx<T> 这种元素类型
#ifndef xpack_adapter_bits_indicator
#define xpack_adapter_bits_indicator
#pragma push_macro("xuser")
#undef  xuser
#define xuser mixc::adapter_bits_indicator::inc
#include"define/base_type.hpp"
#include"instruction/index_of_first_set.hpp"
#include"instruction/index_of_last_set.hpp"
#include"interface/initializer_list.hpp"
#include"interface/unified_seq.hpp"
#include"macro/xforward_constructor.hpp"
#include"macro/xexport.hpp"
#include"macro/xmodify.hpp"
#include"memop/fill.hpp"
#include"memop/zeros.hpp"
#include"meta/has_constructor.hpp"
#include"meta/origin_of.hpp"
#pragma pop_macro("xuser")

namespace mixc::adapter_bits_indicator{
    // 机器位宽
    constexpr bool is_find_last = true;

    /* 函数：设置一个位图树中对应位的状态
     * 参数：
     * - index 为目标操作位的索引
     * - bmp 为位图内存首地址
     * - level_lut 为位图树每一级有多少个 uxx 字
     * - height 为位图树的高度
     * - invoke 为位操作回调，期望签名如下：
     *      bool invoke(uxx * current, uxx index)
     * 补充：
     * - invoke 可能时复位或者置位操作
     * - 从位图树的底层向上层操作
     * - 如果 invoke 复位操作，且在复位后发现当前节点还有其他置位位，则无需再往上级操作
     * - 如果 invoke 置位操作，且在置位前发现当前节点无其他置位位，则无需再往上级操作
     */
    template<class u_t, class callback>
    inline void bmp_set(uxx index, u_t * bmp, const u_t * level_lut, uxx height, callback invoke){
        constexpr
        auto bwidth     = xbitsof(u_t);
        auto bmask      = bwidth - 1;
        auto i          = uxx{};
        auto j          = uxx{};

        while(true){
            if (j = index / bwidth; invoke(xmodify(bmp[j]), u_t(1) << (index & bmask))){
                break;
            }
            if (i + 1 == height){
                break;
            }

            bmp    += level_lut[i];
            i      += 1;
            index   = j;
        }
    }

    /* 函数：在位图树中按指定方式进行位寻找置位位
     * 参数：
     * - bmp 为位图树内存首地址
     * - length 为位图树总长度
     * - level_lut 为位图树每一级有多少个 uxx 字
     * - height 为位图树的高度
     * - invoke 为位操作回调，期望签名如下：
     *      uxx invoke(uxx word)
     * 返回：
     * - 满足指定搜索方式的置位位在位图中的索引
     * - 若未找到则返回 not_exist
     */
    template<class u_t, class callback>
    inline uxx bmp_find(u_t * bmp, uxx length, const u_t * level_lut, uxx height, callback invoke){
        auto offset = u_t{};
        auto index  = u_t{};
        auto p      = bmp + length;

        for(uxx i = height; i-- > 0;){
            p      -= level_lut[i];
            offset  = invoke(p[index]);

            if (offset == not_exist){
                return not_exist;
            }
            index   = index * xbitsof(u_t) | offset;
        }
        return index;
    }

    /* 函数：约束边界，在位图树中按指定方式进行位寻找置位位
     * 参数：
     * - bmp 为位图树内存首地址
     * - level_lut 为位图树每一级有多少个 uxx 字
     * - height 为位图树的高度
     * - invoke 为位操作回调，期望签名如下：
     *      uxx invoke(uxx word)
     * - boundary 为索引的边界，搜寻范围不超过此边界
     * 返回：
     * - 满足指定搜索方式的置位位在位图中的索引
     * - 若未找到则返回 not_exist
     */
    template<class u_t, class callback>
    inline uxx bmp_find(bool is_find_last, u_t * bmp, const u_t * level_lut, uxx height, callback invoke, uxx boundary){
        auto bwidth = xbitsof(u_t);
        auto bmask  = bwidth - 1;
        auto w      = boundary / xbitsof(u_t);

        if (not is_find_last and w >= level_lut[0]){
            return not_exist;
        }

        auto i      = uxx{};
        auto mask   = is_find_last ? u_t(-1) >> (bmask - (boundary & bmask)) : u_t(-1) << (boundary & bmask);
        uxx  r      = invoke(bmp[w] & mask);

        if (r != not_exist){
            return w * xbitsof(u_t) | r;
        }

        while(i < height - 1){
            // 从下向上
            bmp    += level_lut[i];
            mask    = is_find_last ? u_t(-1) >> (bwidth - (w & bmask)) : u_t(-1) << ((w & bmask) + 1);
            w      /= xbitsof(u_t);
            r       = invoke(bmp[w] & mask);

            if (r == not_exist){
                i  += 1;
                continue;
            }

            // 从上向下
            do{
                bmp -= level_lut[i];
                w    = w * xbitsof(u_t) | r;
                r    = invoke(bmp[w]);
            } while(i-- != 0);

            return w * xbitsof(u_t) | r;
        }
        return not_exist;
    }

    // protected 成员无法直接访问
    // template<class type_t>
    // concept can_bits_indicator = requires(type_t value, uxxp bmp, const uxx * level_lut, uxx size, uxx height){
    //     bmp         = value->bmp;
    //     level_lut   = value->level_lut;
    //     size        = value->size;
    //     height      = value->height;
    // };

    template<class final_t>
    xstruct(
        xtmpl(bits_indicator, final_t)
    )
        /* 函数：复位所有位 */
        final_t & clear(){
            inc::zeros(xthex->bmp, xthex->size * sizeof(*xthex->bmp));
            return xthex;
        }

        /* 函数：将指定索引的位置位
         * 参数：
         * - index 为要置位的索引
         */
        final_t & set(uxx index){
            using u_t = inc::origin_of<decltype(*xthex->bmp)>;
            bmp_set<u_t>(index, xthex->bmp, xthex->level_lut, xthex->height, [](auto * p, auto val){
                bool has_set = *p != 0;
                *p          |= val;
                return has_set;
            });
            return xthex;
        }

        /* 函数：将指定索引的位设置成 value 值
         * 参数：
         * - index 为要置位的索引
         * - value 为要设置的值
         */
        final_t & set(uxx index, bool value){
            value ? set(index) : reset(index);
            return xthex;
        }

        final_t & set_all(){
            // 这里 size 表示 inc::fill 的填充个数，单位是 uxx
            using u_t   = inc::origin_of<decltype(*xthex->bmp)>;
            inc::fill((u_t *)xthex->bmp, u_t(-1), xthex->size);
            return xthex;
        }

        final_t & reset_all(){
            // 这里 size 表示 inc::fill 的填充个数，单位是 uxx
            using u_t   = inc::origin_of<decltype(*xthex->bmp)>;
            inc::fill((u_t *)xthex->bmp, u_t(0), xthex->size);
            return xthex;
        }

        /* 函数：根据索引数组依次将指定索引的位置位
         * 参数：
         * - index_list 为支持 inc::can_unified_seqlize 接口的对象
         */
        template<inc::can_unified_seqlize seq_t = inc::initializer_list<uxx>>
        final_t & set(seq_t && index_list){
            auto list = inc::unified_seq<seq_t>(index_list);

            for(uxx i = 0, length = list->length; i < length; i++){
                set(list[i]);
            }
            return xthex;
        }

        /* 函数：将指定索引的位复位
         * 参数：
         * - index 为要置位的索引
         */
        final_t & reset(uxx index){
            using u_t = inc::origin_of<decltype(*xthex->bmp)>;
            bmp_set<u_t>(index, xthex->bmp, xthex->level_lut, xthex->height, [](auto * p, auto val){
                *p &= ~val;
                return *p != 0;
            });
            return xthex;
        }

        /* 函数：根据索引数组依次将指定索引的位复位
         * 参数：
         * - index_list 为支持 inc::can_unified_seqlize 接口的对象
         */
        template<inc::can_unified_seqlize seq_t = inc::initializer_list<uxx>>
        final_t & reset(seq_t && index_list){
            auto list = inc::unified_seq<seq_t>(index_list);

            for(uxx i = 0, length = list->length; i < length; i++){
                reset(list[i]);
            }
            return xthex;
        }

        /* 函数：得到指定索引的位状态
         * 参数：
         * - index 目标索引
         */
        bool get(uxx index){
            using u_t   = inc::origin_of<decltype(*xthex->bmp)>;
            auto bwidth = xbitsof(u_t);
            auto bmask  = bwidth - 1;
            auto i      = index / xbitsof(u_t);
            auto m      = u_t(1) << (index & bmask);
            return (xthex->bmp[i] & m) != 0;
        }

        /* 函数：得到第一个置位位索引并对它复位 */
        uxx pop_first(){
            if (uxx index = index_of_first_set(); index != not_exist){
                reset(index);
                return index;
            }
            return not_exist;
        }

        /* 函数：得到最后一个置位位索引并对它复位 */
        uxx pop_last(){
            if (uxx index = index_of_last_set(); index != not_exist){
                reset(index);
                return index;
            }
            return not_exist;
        }

        /* 函数：得到第一个置位位索引 */
        uxx index_of_first_set() const {
            using u_t   = inc::origin_of<decltype(*xthex->bmp)>;
            return bmp_find<u_t>(
                xthex->bmp,
                xthex->size,
                xthex->level_lut,
                xthex->height,
                & inc::index_of_first_set<u_t>
            );
        }

        /* 函数：从指定索引开始寻找第一个置位位索引
         * 参数：
         * - start_boundary 为搜索的起始索引
         */
        uxx index_of_first_set(uxx start_boundary) const {
            using u_t   = inc::origin_of<decltype(*xthex->bmp)>;
            return bmp_find<u_t>(
                not is_find_last,
                xthex->bmp,
                xthex->level_lut,
                xthex->height,
                & inc::index_of_first_set<u_t>, start_boundary
            );
        }

        /* 函数：得到最后一个置位位索引 */
        uxx index_of_last_set() const {
            using u_t   = inc::origin_of<decltype(*xthex->bmp)>;
            return bmp_find<u_t>(
                xthex->bmp,
                xthex->size,
                xthex->level_lut,
                xthex->height,
                & inc::index_of_last_set<u_t>
            );
        }

        /* 函数：从指定索引开始寻找最后一个置位位索引
         * 参数：
         * - end_boundary 为搜索的起始索引，从后往前搜索
         */
        uxx index_of_last_set(uxx end_boundary) const {
            using u_t   = inc::origin_of<decltype(*xthex->bmp)>;
            return bmp_find<u_t>(
                is_find_last,
                xthex->bmp,
                xthex->level_lut,
                xthex->height,
                & inc::index_of_last_set<u_t>, end_boundary
            );
        }
    $
}

#endif

xexport(mixc::adapter_bits_indicator::bits_indicator)

